iT邦幫忙

DAY 15
4

emacs的30天學習筆記系列 第 36

懷舊C語言:1988 The C Programming Language 2nd Edition(PART V)

  • 分享至 

  • xImage
  •  

這本輕薄的小書,書中摘錄了其他計算機學科的一些項目,兩位作者有意識到這一點,
所以在這本以如果使用C語言的教學書中,對很多較深入(困難)的程式,常常是由淺入深寫個好幾版給讀者,讓讀者基本上只要用(Find/Replace)的功能,來替換掉一些字,或是加上一些IF/THEN/ELSE的判斷就可以完成習題。當然不少習題還是很困難 。

自從PASCAL之父,http://en.wikipedia.org/wiki/Niklaus_Wirth
於1975年寫下了一本經典書(筆者那時才三歲),"Algorithms + Data Structures = Programs",書名也是一句經典名句。10年過去,20年過去,到現在,
雖然現在的程式員,唸書時還是有修演算法,資料結構,但是在工作上,幾乎已經淪為call api了,變成用演算法,資料結構的程式員,變成C語言程式員的工作內容,其他語言的程式員,
一來因為物件導向,二來因為framework過度封裝,所以雖然寫程式,
但是不太用演算法,資料結構。以36年前的定義來說,筆者有時覺得自己還算在寫程式嗎?
寫出來的不是程式,到底是什麼呢?

愈來愈發現,如果想要原創一些程式,或是寫一些有用的程式,只有COPY+PASTE,或是
call api真的是做不到這些事。

以這本1988年第二版的書,雖是講C語言的教學書,書中範例,仍然和**"Algorithms + Data Structures = Programs"的精神很像,仍是用演算法,資料結構為範例,讓學生從中練習。不知是否有讀者因為這句話"Algorithms + Data Structures = Programs"是看原書 。基本上這不是一本教如何使用pascal(基本上佔的篇幅)的書,而是教如果做一個能編譯 pascal的編譯器的書。pascal影響後世深遠,但是好像比較少影響到C語言,
而PASCAL 現在主要以delphi(object pascal)和PL/SQL(ORACLE的 SQL FUNCTION SQL PROCEDURE)為主,還活得好好的。甚至也gcc化了。可以
google gcc pascal**。

想想以前的書,寫的內容是如何寫編譯器,那是龍書等級的難度,和現在的快快樂樂,圖by圖的書,真得差很多。

本書,談及了演算法,快速排序法(quick sort),二元排序法。遞迴的使用。
一部分BNF文法(grammer),自參考的結構(link list)。
這些古典的思維,現在都被視為偏難的學科,猜想23年前,應該也有這種學生學習上的問題,所以兩位作者都先寫好,讓學生參照著改,而不是從頭到尾無中生有的寫出來。

間斷了幾天,是在想一個讓自己比較有樂趣的用gcc方式。除了寫習題之外,還能有其他的寫code樂趣,不然自己都覺得無聊,那能期望別人有趣呢??

以下試整理書中所提的快速排序法(qsort).
在第四章,講到遞迴,作者說第二個關於遞迴的good example,是1962年由C.A.R. Hoare研發的快速排序法,而快速排序法,看書中的簡潔說明,還不如看WIKI http://en.wikipedia.org/wiki/Quick_sort,有動畫的。
快速排序法,理解上有點困難,而實作起來的code很精簡,但其中道理很深。

作者寫了一個可能不是最的快速排序法,但可能是最簡單的(或其中之一)。

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left; /* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* restore partition elem */
qsort(v, left, last-1);
qsort(v, last+1, right);
}
/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}

就像協定一樣,有時候實作演算法也怕理解錯誤,導致實作錯誤,或沒實作到。
快速演算法,有用到分割。把一堆數,分成一半,一半來處理,這在其他排序演算法也有類似的思維,交換,從最入門的氣泡排序法,就有交換,不交換,怎麼排大小呢?所以這是基本動作,再來是遞迴,這等於沒講,雖然可以不用遞迴,只是快速排序法,基本上,不容易從他的名稱**(快速)猜出它的動作特性,尤其是幾個排序法一起比較時,常常你會覺得他和merge**合併排序有點像,又和另一排序有點像。

有了之前的經驗,筆者很容易換成指標版,就是把v[]換成 *v, 把v[i]換成 *(v+i),因為做久了,會誤以為v[]= *v,v[i]=(v+i),不知道大家會不會有這種誤解,雖從程式結果來看,不是不對,但還是有不同的,之後會有些範例來說明。

測試程式:

#include <stdio.h>
#define N 10 
void qsort(int v[], int left, int right);
void swap(int v[], int i, int j);

main()
{

int unsort[N]={8,2,9,7,1,3,6,5,0,4}; 
qsort( unsort, 0,9);
int i;
for ( i=0;i<N ;i++) 
printf("%d \n", unsort[i]);

}

接著是 中階版的qsort。


上一篇
Web Service 閒談- 1998年 XML-RPC談起
下一篇
懷舊C語言:1988 The C Programming Language 2nd Edition(PART VI)
系列文
emacs的30天學習筆記38
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

0
pqr0007
iT邦研究生 1 級 ‧ 2011-11-14 22:14:01

sort of difficult!...

0
chiounan
iT邦研究生 1 級 ‧ 2011-11-15 09:29:44

很好的分享。
如果程式碼可以有適當的style,就更方便閱讀了。

我要留言

立即登入留言